Communication networks comprise a large number of interconnected network nodes, such as terminals, routers and switches. Data is communicated through such a network by passing protocol data units, such as Internet Protocol (IP) packets, Ethernet frames or data cells between nodes. A particular protocol data unit may travel along a path through many such nodes and communication links and a network of this kind should efficiently route the protocol data units between nodes.
In-order to route packets, the network topology needs to be known by all nodes in the network. Network topology information, which can be used to route data units, can be exchanged between nodes using a variety of protocols. With link state routing protocols each router advertises information about links to which it is connected and update messages known as Link State Advertisements (LSAs) are sent between routers. Link State routers maintain topology databases containing representations of every link and router in the network and a state for each element. One link state protocol is Open Shortest Path First (OSPF), which is described in RFC2328. Routing protocols such as OSPF work well in small networks but they are less suited to larger networks, and networks where the topology changes frequently. One situation where the network topology can frequently change is in wireless ad-hoc networks. The topology may change quite often, and even if nodes are not being added, removed or moved transient radio interference will cause links between nodes to vary in both their capacity and their availability. The cost, in terms of bandwidth, of updating each node's view of the network topology is high. If the number of network nodes is large or the topology is changing, for example due to wireless links forming and breaking as radio reception quality varies, the number of updates required will be large, resulting in significant bandwidth consumption by the routing protocol.
One known way of coping with this problem is to divide OSPF routers into areas. Routers within each area are configured with information about other routers within their own area. Special routers, known as border routers, interwork between areas. While this scheme can reduce the number of LSAs that are sent between nodes this kind of sub-division requires a centralized management function. This requirement does not lend itself to ad-hoc networks, where it is desirable that nodes should not require centralized management or configuration.
A U.S. patent application with U.S. Ser. No. 10/757,139, filed 14 Jan. 2004, the contents of which are incorporated herein by reference, describes how link state advertisement messages are propagated a limited distance from their source. This creates the notion of a routing radius, which is defined for each node and includes the nodes whose distance is no more than some predefined limit. With this enhancement to OSPF, each node will only know the topology of the network within its routing radius and nodes are updated about topological changes only within that radius. Thus, even though a network can be arbitrarily large, the updates are only propagated relatively locally.
While this enhancement can improve the performance of networks, it can cause problems in situations where the network comprises a mix of conventional OSPF routers and routers which operate with the radius-restricted enhancement.
The present invention seeks to improve the operation of a network in which a mix of router types are present.